#include<vector>
using namespace std;
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.size() == 0) return -1;
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] > target) {
                if (nums[mid] >= nums[0]&& nums[0] > target)
                    left = mid + 1;
                else
                    right = mid;
            }
            else {
                if (nums[mid] < nums[0]&& nums[0] <= target) 
                    right = mid;
                else
                    left = mid + 1;
            }
        }
        return -1;
    }
};

int main() {
    vector<int>res = {3,1 };
    Solution sol;
    sol.search(res, 3);
}